![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
Our solution is as follows: If we flip the same bits in g(C) as in g(D), then the sum g(C) + g(D) will be unchanged, and as a result, the effect of the input difference in c1, d1 will also be unchanged. Let x3, y3 be the bytes that actually go into the S-box s3 in the two g functions. We control c3, d3, but their values axe XORed with some unknown bytes before being used as x3, y3. Thus,
x3 = c3 ⊕ z3
y3 = d3 ⊕ z4
We need to be able to choose c3, d3 so that x3 = y3. If we ever did that, then we could generate 255 additional cases where y3 = z3, simply by XORing 1,...,255 into both c3 and d3. Now, if we knew z3 ⊕ z4, we could choose any c3 value we liked, and then set d3 = c3 ⊕ z3 ⊕ z4, giving us x3 = y3. We thus try all 256 possible values for z3 ⊕ z4. One of those values is right; we can use it to take a single right pair, and produce 255 more just like it. This is done by keeping A and B constant, and by choosing
C = (c0, c1, c2, c3 ⊕ i)
D = (d0, d1, d2, d3 ⊕ i ⊕ z3 ⊕ z4)
C* = (c0, c*1, c2, c3 ⊕ i)
D* = (d0, d*1, d2, d3 ⊕ i ⊕ z3 ⊕ z4)
where c1, d1, and c*1, d*1 are the bytes changed in the original right pair. For each potential right pair, we thus generate 256 pairs of text according to the above formula for each guess about z3 ⊕ z4. This means that each potential right pair generates 256 batches of 256 pairs of plaintexts (and corresponding pairs of ciphertexts), or a total of 216 plaintext pairs. Thus, n0 = 256.
Deriving a Right Pair from a Partial Right Pair. Suppose we have a pair of texts, (C, D), (C*, D*), such that g(C) ⊕ g(C*) = g(D) ⊕ g(D*), with that XOR difference having Hamming weight of 8. In most (255/256) cases, this wont be a right pair, because g(C) + g(D) ≠ g(C*) + g(D*). To turn this into a right pair, some of the bits in g(C) which axe covered by the XOR difference need to be flipped. We thus choose the available bytes, c0 and c2, and vary both bytes randomly in different texts. After about 256 different random c0, c2 choices, we expect to derive a real right pair from the partial right pair. Naturally, most of the pairs we generate will not be right pairs, and we wont be able to distinguish them from wrong pairs until we mount the attack.
Finding a Single Partial Right Pair. A partial right pair can be found by getting the same XOR difference out from the S-box determined by c1 and also by d1. We dont know the S-box these are going through, but simulations show that if we try i, i ⊕ δ as a pair of inputs into a random 8-bit-wide bijective S-box, s, we have a probability of 1/2 of getting any desired output XOR difference. If there axe three XOR differences that lead, after the MDS matrix is applied, to 8-bit XOR differences, then the probability is thus 7/8 that this approach will work to find a partial right pair.
We have the same complications we did above: we control c1, d1, but we need to control x1 = c1 ⊕ z1,y1 = d1 ⊕ z2, the inputs to the S-boxes in the two g functions. Similarly to the way we dealt with this above, we end up guessing z1 ⊕ z2. The result is that we generate 216 plaintext pairs, of which at least one is almost certainly a partial right pair. Thus, n2 = 216.
Testing a Batch of Plaintext Pairs. We generate n0n1n2 = 2828216 = 232 batches of plaintext pairs. During our attack, we must guess as much of the key material as is required, and for each guess, we must test each batch to see if it is made up of only right pairs. The probability of a randomly-selected key giving us a false positivethat is, a batch that appears to be right but is notis 2-256. This probability is low enough that we never expect a single false positive.
We now consider the difficulty of testing one such batch of plaintext pairs. The question is how many trial partial decryptions we must do for each batch, on average, before determining that the batch is not made up of only right pairs. For a guessed partial key, each batch will yield a sequence of 256 bits; in the batch of right pairs, they will all be the expected bit. However, for each batch, we can stop searching as soon as we find a single bit that is different than the others. The expected number of trial partial decryptions required per batch is thus
2 · 1/2 + 3 · 1/4 + 4 · 1/8 + ··· + (n + 1) · 1/2n ≈ 3
Each partial decryption is less work than a full encryption. We take n3 = 1 for our estimates, which corresponds to each partial decryption being one-third as much work as a full encryption.
To mount the attack, we must determine what key material must be guessed to check our batches. Consider a 5-round Twofish variant without whitening and without the 1-bit rotations. In this case, we need only guess S. Recall that in a right pair, we know the difference in only one bitthe low-order bit of D in this caseat the input to the fifth round. After guessing S, we can compute the value of the g function that uses A as its input in the fifth round. The low-order bit of this is XORed with the low-order bit of the corresponding subkey, and then XORed into the bit whose difference we know. Knowledge of the low-order bit of that g output thus gives us the desired bit difference.
To extend this another round, we must also guess the subkey in the sixth round that affects the value XORed into A. Because we only have to get the low bit of D, we need not compute the B value input into the fifth rounds F function at all. This requires 232 additional work.
To extend this one more round, we must guess the whole set of round subkeys in the next round. This requires 264 additional work.
Five-round Twofish consists of ten g computations and a little extra work. To be conservative, we can consider each g computation to be 1/8 of a trial encryption.
Key Length | Rounds | Work(equiv. trial encs.) |
---|
128 | 5 | 230 · 264 = 294 |
128 | 6 | 230 · 296 = 2126 |
192 | 5 | 230 · 296 = 2126 |
192 | 6 | 230 · 2128 = 2158 |
256 | 5 | 230 · 2128 = 2158 |
256 | 6 | 230 · 2160 = 2190 |
256 | 7 | 230 · 2224 = 2254 |
Table 9.3. Differential Attack Results against a Variant with No Whitening and No Rotations
Key Length | Rounds | Work(equiv. trial encs.) |
---|
128 | 5 | 230 · 274 = 2104 | |
128 | 6 | 230 · 2138 = 2166 | (No longer useful.) |
192 | 5 | 230 · 2106 = 2136 | |
192 | 6 | 230 · 2170 = 2200 | (No longer useful.) |
256 | 5 | 230 · 2138 = 2168 | |
256 | 6 | 230 · 2202 = 2232 | |
256 | 7 | 230 · 2266 = 2296 | (No longer useful.9) |
Table 9.4. Differential Attack Results against a Variant with No Whitening
Thus, for five- to seven-round Twofish with no whitening and no 1-bit rotates, we have the results summarized in Table 9.3.2 (Note that all of these results are for 241 chosen plaintexts.)
2We are indebted to Eli Biham for the suggestion of guessing the whole last rounds subkeys for the 256-bit key.
When we add back in the 1-bit rotates, the attacks grow substantially harder. (Interestingly, though we put the 1-bit rotates in because of concerns about the byte structure, so far, the 1-bit rotates have complicated several attacks based on exploiting properties of the low bit of one of the PHT words.) We must now learn both g function outputs in the fifth round, as well as guessing the high-order 10 or so bits of round subkey used to alter the value XORed into D in the fifth round. We list the resulting attack complexities in Table 9.4.
The whitening also adds a little difficulty. When combined with the 1-bit rotates, we get the results summarized in Table 9.5. We note that there are straightforward differential attacks on four rounds that work despite the 1-bit rotations and whitening, but they involve using only the (0, X) → (?, (?, 1)) differential.
Key Length | Rounds | Work(equiv. trial encs.) |
---|
128 | 5 | 230 · 2128 = 2158 | (No longer useful.) |
192 | 5 | 230 · 2170 = 2200 | (No longer useful.) |
256 | 5 | 230 · 2202 = 2232 |
Table 9.5.3 Differential Attack Results against Reduced Rounds
Key Length | Rounds | Work(equiv. trial encs.) |
---|
all | 6 | 230 · 232 = 262 |
all | 7 | 230 · 296 = 2126 |
192 & 256 | 8 | 230 · 2160 = 2190 |
256 | 9 | 230 · 2224 = 2254 |
Table 9.6. Differential Attack Results on a Variant with Known S and No Rotations
Finally, we can consider the difficulty of this attack on a Twofish variant with a fixed, known S value and no 1-bit rotates. In this case, we have the difficulties results listed in Table 9.6.
Again, this demonstrates how the additional key material in the key-dependent S-boxes adds to the practical difficulty of an attack. Additionally, with fixed S-boxes, it may be possible for the attacker to get a substantial improvement, perhaps by as much as a factor of 256, on the number of plain-text batches he must request. This would reduce the plaintext requirement and the work factors on all these attacks by the same factor.
Previous | Table of Contents | Next |